// https://leetcode.cn/problems/word-search/

// 题干：给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。
//       如果 word 存在于网格中，返回 true ；否则，返回 false 。
//       单词必须按照字母顺序，通过相邻的单元格内的字母构成，
//       其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

// 示例：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "AABCCED"
//      输出：true

// 碎语：三军未动，决策树先行
//       某一层的作用是匹配下一个字符
//       二维矩阵搜索中，不能走重复的路

#include <bits/stdc++.h>
using namespace std;

class Solution
{
    bool visit[7][7]; // 也可以修改原始矩阵的值，毕竟会浪费空间，但要慎用
    int m, n;
public:
    bool exist(vector<vector<char>>& board, string word)
    {
        memset(visit, 0, sizeof(visit));
        m = board.size(), n = board[0].size();

        for (int i = 0 ; i < m ; i++){
            for (int j = 0 ; j < n ; j++){
                if (board[i][j] == word[0]){
                    visit[i][j] = true;
                    if(dfs(board, i, j, word, 1)) return true; // 根据board这个棋盘，从i，j这个位置开始，匹配word的第k个字符
                    visit[i][j] = false;
                }
            }
        }
        return false;
    }

    int dx[4] = {0, 0, -1, 1};
    int dy[4] = {1, -1, 0, 0};

    bool dfs(vector<vector<char>>& board, int i, int j, string& word, int pos)
    {
        if (pos == word.size()) return true;

        for (int k = 0 ; k < 4 ; k++){
            int x = i + dx[k], y = j + dy[k];
            if (x >= 0 && x < m && y >= 0 && y < n && !visit[x][y] && board[x][y] == word[pos]){
                visit[x][y] = true;
                if (dfs(board, x, y, word, pos + 1)) return true;
                visit[x][y] = false;
            }
        }
        return false;
    }
};

int main()
{
    Solution sol;
    vector<vector<char>> board = {{'A', 'B', 'C', 'E'}, {'S', 'F', 'C', 'S'}, {'A', 'D', 'E', 'E'}};
    string word = "ABCCED";

    cout << sol.exist(board, word) << endl;

    return 0;
}